Diffie–Hellman thiết lập bí mật chung để sử dụng cho trao đổi dữ liệu an toàn trên một kênh truyền thông công cộng không an toàn. Sơ đồ sau đây minh họa ý tưởng cơ bản của việc trao đổi khóa thông qua ví dụ về màu sơn.

Ý tưởng cơ bản

Điểm chủ chốt của ý tưởng này là Alice và Bob trao đổi màu sơn bí mật thông qua hỗn hợp sơn.

• Đầu tiên Alice và Bob trộn màu đã biết chung (màu vàng) với màu bí mật riêng của mỗi người.
• Sau đó, mỗi người chuyển hỗn hợp của mình tới người kia thông qua một kênh vận chuyển công cộng.
• Khi nhận được hỗn hợp của người kia, mỗi người sẽ trộn thêm với màu bí mật của riêng mình và nhận được hỗn hợp cuối cùng.

Hỗn hợp sơn cuối cùng là hoàn toàn giống nhau cho cả hai người và chỉ có riêng hai người biết. Mấu chốt ở đây là đối với một người ngoài sẽ rất khó (về mặt tính toán) cho họ để tìm ra được bí mật chung của hai người (nghĩa là hỗn hợp cuối cùng). Alice và Bob sẽ sử dụng bí mật chung này để mã hóa và giải mã dữ liệu truyền trên kênh công cộng. Lưu ý, màu sơn đầu tiên (màu vàng) có thể tùy ý lựa chọn, nhưng được thỏa thuận trước giữa Alice và Bob. Màu sơn này cũng có thể được giả sử là không bí mật đối với người thứ ba mà không làm lộ bí mật chung cuối cùng của Alice và Bob.

Giao thức được diễn giải dưới dạng toán học như sau:

Giao thức sử dụng nhóm nhân số nguyên modulo p, trong đó p số nguyên tố, và g là căn nguyên thủy mod p. Trong ví dụ dưới đây, giá trị không bí mật được viết bằng màu xanh, và giá trị bí mật viết bằng màu đỏ:

1. Alice và Bob thỏa thuận sử dụng chung một số nguyên tố p=23 và căn nguyên thủy g=5.
2. Alice chọn một số nguyên bí mật a=6, và gửi cho Bob giá trị A = ga mod p
   • A = 56 mod 23
   • A = 15,625 mod 23
   • A = 8
3. Bob chọn một số nguyên bí mật b=15, và gửi cho Alice giá trị B = gb mod p
   • B = 515 mod 23
   • B = 30,517,578,125 mod 23
   • B = 19
4. Alice tính s = B a mod p
   • s = 196 mod 23
   • s = 47,045,881 mod 23
   • s = 2
5. Bob tính s = A b mod p
   • s = 815 mod 23
   • s = 35,184,372,088,832 mod 23
   • s = 2
6. Như vậy Alice và Bob cùng chia sẻ bí mật chung là số 2 vì 6*15 cũng bằng 15*6.

Cả Alice và Bob đều có được giá trị chung cuối cùng vì (ga)b = (gb)a mod p. Lưu ý rằng chỉ có a, b và gab = gba mod p là được giữ bí mật. Tất cả các giá trị khác như p, g, ga mod p và gb mod p được truyền công khai. Sau khi Alice và Bob tính được bí mật chung, cả hai có thể sử dụng nó làm khóa mã hóa chung chỉ có hai người biết để gửi dữ liệu trên kênh truyền thông mở.

Trong thực tế để giao thức được an toàn, người ta sử dụng giá trị lớn hơn nhiều cho a, b, và p, vì trong ví dụ trên chỉ có tổng cộng 23 kết quả khác nhau cho n mod 23 (do đó kẻ tấn công chỉ cần thử hết 23 trường hợp là tìm ra khóa bí mật). Nếu số nguyên tố p có ít nhất 300 chữ số, còn a và b có ít nhất 100 chữ số, thì ngay cả những máy tính hiện đại nhất hiện nay cũng không thể tìm được a nếu chỉ biết g, p, gb mod p và ga mod p. Bài toán này, gọi là bài toán Lôgarit rời rạc, hiện chưa có cách giải hiệu quả bằng máy tính (vì vậy được sử dụng để tạo khóa công khai).

Lưu ý, g không cần thiết là một căn nguyên thủy có giá trị lớn. Trong thực tế người ta hay sử dụng các giá trị 2, 3 hoặc 5.

Mô tả giao thức

Sau đây là mô tả khái quát của giao thức.

Thiết lập khóa

1. Alice và Bob thỏa thuận sử dụng chung một nhóm cyclic hữu hạn G và một phần tử sinh g của G. Phần tử sinh g công khai với tất cả mọi người, kể cả kẻ tấn công. Dưới đây chúng ta giả sử nhóm G là nhóm nhân.
2. Alice chọn một số tự nhiên ngẫu nhiên a và gửi ga mod p cho Bob.
3. Bob chọn một số tự nhiên ngẫu nhiên b và gửi gb mod p cho Alice.
4. Alice tính (gb)a mod p.
5. Bob tính (ga)b mod p.

Vì giá trị (gb)a và (ga)b là bằng nhau (do nhóm G có tính kết hợp), cả Alice và Bob đều tính được giá trị gab và có thể sử dụng nó cho khóa bí mật chung.

Mã hóa

Thông điệp m trước khi được gửi đi bởi Alice (hoặc Bob) sẽ được mã hóa thành mgab.

Giải mã

Để giải mã thông điệp m, gửi dưới dạng mgab, Bob (hoặc Alice) phải tính được giá trị (gab)-1. Giá trị (gab)-1 được tính như sau:Vì Bob biết |G|, b, và ga, mặt khác theo định lý Lagrange trong lý thuyết nhóm ta có x|G| = 1 với mọi x thuộc G,nên Bob tính được (ga)|G|-b = ga(|G|-b) = ga|G|-ab = ga|G|g-ab = (g|G|)ag-ab=1ag-ab=g-ab=(gab)-1.

Việc giải mã bây giờ trở nên dễ dàng: Bob sử dụng (gab)-1 đã tính và phục hồi thông điệp nguyên thủy bằng cách tính: mgab(gab)-1 = m(1) = m.